/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 19:11
 */
public class test_6 {

    int minFallingPathSum(int[][] matrix) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果

        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        {
            for (int i = 1; i <= n; i++)
                dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;

            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1],
                            dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            int ret = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++)
                ret = Math.min(ret, dp[n][j]);
            return ret;
        }

    }
}
